/**
 * @param {string} n
 * @return {string}
 */
export var smallestGoodBase = function (n) {
  // n的最大值超过js的最大安全整数范围所以改用BigInt
  n = BigInt(n)
  //先确定 a 的最大值，因为Math.log2的参数不能是 BigInt，所以只能从小到大去算a的 i 次方
  let a_max
  for (let i = 1; ; i++) {
    if (Math.pow(2, i) > n) {
      a_max = BigInt(i) + 1n
      break
    }
  }
  console.log('a_max:' + a_max)
  //a 不能等于 1，因为 a 等于 1 的时候，k 就等于 n 了。但是任意给定一个 n，都可以存在k 等于 n-1，a 等于 2，使得题目成立
  for (let a = a_max; a >= 2n; a--) {
    //k >= 2 && k <= n - 1, 可以使用二分查找的方式
    let start = 2n
    let end = n - 1n
    let k
    // eslint-disable-next-line no-constant-condition
    while (true) {
      k = (start + end) / 2n
      let result = (k ** a - 1n) / (k - 1n)
      if (result === n) return String(k)
      else if (result > n) {
        end = k - 1n
      } else if (result < n) {
        start = k + 1n
      }
      if (start > end) break
    }
  }
}

// 数学方法
export var smallestGoodBase2 = function (n) {
  const nVal = parseInt(n)
  const mMax = Math.floor(Math.log(nVal) / Math.log(2))
  for (let m = mMax; m > 1; m--) {
    const k = BigInt(Math.floor(Math.pow(nVal, 1.0 / m)))
    if (k > 1) {
      let mul = BigInt(1),
        sum = BigInt(1)
      for (let i = 1; i <= m; i++) {
        mul *= k
        sum += mul
      }
      if (sum === BigInt(n)) {
        return k + ''
      }
    }
  }
  return BigInt(n) - BigInt(1) + ''
}
